[[abstract]]Let T be a text of length n and P be a pattern of length m, both strings over a fixed finite alphabet A. The k-difference (k-mismatch, respectively) problem is to find all occurrences of P in T that have edit distance (Hamming distance, respectively) at most k from P. In this paper we investigate a well-studied case in which T is fixed and preprocessed into an indexing data structure so that any pattern query can be answered faster. We give a solution using an O(nlogn) bits indexing data structure with O(|A|kmk·max(k,logn) +occ) query time, where occ is the number of occurrences. The best previous result requires O(nlogn) bits indexing data structure and gives O(|A|kmk+2+occ) query time. Our solution also allows us to exploit compressed suffix arrays to reduce the indexing space to O(n) bits, while increasing the query time by an O(logn) factor only.
展开▼
机译：[[摘要]]令T为长度为n的文本，P为长度为m的模式，两个字符串均位于固定的有限字母A上。k差异（分别为k不匹配）问题是找到所有出现的P在T中具有距P最多k的编辑距离（分别为汉明距离）。在本文中，我们研究了一种经过充分研究的情况，其中T被固定并预处理为索引数据结构，以便可以更快地回答任何模式查询。我们给出一个使用O（nlogn）位索引数据结构和O（| A | kmk·max（k，logn）+ occ）查询时间的解决方案，其中occ是出现的次数。最好的先前结果需要O（nlogn）位索引数据结构，并给出O（| A | kmk + 2 + occ）查询时间。我们的解决方案还允许我们利用压缩后缀数组将索引空间减少到O（n）位，同时仅将查询时间增加O（logn）因子。
展开▼
